#include "node.h"

class Solution {
public:
    /**
     * @param head Node类 
     * @param m int整型 
     * @param n int整型 
     * @return Node类
     */
    Node* reverseBetween(Node* head, int m, int n) {
        //! 递归终止体检
        if (!head || m == n) return head;

        Node* dummy = new Node(0);
        dummy->next = head;
        Node* pre   = dummy;


        //! 找到第 m-1 个节点
        for (int i = 1; i < m; ++i) {
            pre = pre->next;
        }


        //! 开始翻转从 m 到 n 的节点
        Node* start = pre->next;   // 第 m 个节点
        Node* then  = start->next; // 第 m+1 个节点

        for (int i = 0; i < n - m; ++i) {
            start->next = then->next;
            then->next = pre->next;
            pre->next = then;
            then = start->next;
        }


        //! 返回新的头节点
        Node* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};